Algoritmo ricorsivo

Viene detto algoritmo ricorsivo un algoritmo espresso in termini di se stesso.

Questo tipo di algoritmi risulta particolarmente utile per eseguire dei compiti ripetitivi su di un set di input variabili. L'algoritmo richiama se stesso generando un ciclo di chiamate che ha termine al verificarsi di una condizione particolare che chiameremo caso di base, coincidente, in genere, con il presentarsi di particolari valori di input. La tecnica ricorsiva permette di scrivere algoritmi eleganti e sintetici per molti tipi di problemi comuni, sarà tuttavia opportuno verificarne di volta in volta l'efficienza rispetto ad altri tipi di soluzioni, come per esempio cicli elementari.

Per chiarire il concetto useremo un esempio di tipo matematico, il calcolo del fattoriale di un numero n.

Chiameremo fattoriale di n e scrivermo n!, il prodotto dei primi n numeri naturali, ottenuto come segue:

         0! = 1;
         n! = 1 * 2 * 3 * ...... * n-1 * n;       per n > 0.

Modificando leggermente la definizione, ci si accorge di come sia possibile darne una versione ricorsiva; Sia a tal proposito:

         n! = (1 * 2 * 3 * ...... * n-1) * n;

si ottiene,

         n! = (n-1)! * n;

da cui, iterando,

         n! = (n-2)! * n-1 * n,

continuando ad iterare la definizione, arriveremo ai casi di base per i quali il risultato cercato è noto,

         0! = 1! = 1.

Siamo adesso in grado di dare un algoritmo ricorsivo che chiameremo FATT, per il calcolo del fattoriale. Si osservi che la notazione utilizzata distingue tra il simbolo x == y, per indicare uguglianza tra i due valori ed il simbolo x = y, per indicare che alla variabile x sarà assegnato il valore di y, così come per il Linguaggio C:

      FATT (n)
         if n 0 or n 1
            return 1 
         else
            return n * FATT (n-1)

Quando l'algoritmo viene eseguito la prima volta, il valore di n viene confrontato con 0 e con 1, nel caso in cui il valore sia diverso, la procedura viene chiamata ricorsivamente su valori più piccoli sino a quando n non risulta uguale ad 1, nel qual caso il risultato è noto e può essere restituito dalla funzione attuale a quella che l'aveva in precedenza chiamata. I risultati restituiti da ognuna delle procedure ricorsive vengono di volta in volta moltiplicati. Il penultimo valore restituito sarà proprio uguale ad (n-1)!, quest'ultimo verrà moltiplicato per n e l'algoritmo potrà restituire il risultato cercato.

A scopo esplicativo e didattico, viene fornito di seguito un algoritmo per il calcolo del fattoriale che sfrutta un approccio di tipo iterativo:

      FATTiterativo (n)
         fatt = 1
         i = 2
         while i <= n 
            fatt = fatt * i	
            i + 1	
         return fatt

Tipi di ricorsione

Esistono vari tipi di ricorsione. Si parla di mutua ricorsione quando nell'algoritmo una funzione ne richiama un'altra che a sua volta richiama la prima, altrimenti si parla di ricorsione diretta.

Altra distinzione � quella fra ricorsione lineare, che si ha quando vi � solo una chiamata ricorsiva all'interno della funzione, e non lineare nel caso in cui le chiamate ricorsive siano pi� di una.

La distinzione pi� importante ai fini pratici si ha fra ricorsione di coda (tail recursion) e ricorsione non di coda. Si parla di ricorsione di coda quando la chiamata ricorsiva � l'ultima istruzione eseguita nella funzione. Questo tipo di algoritmo ricorsivo � possibile trasformarlo semplicemente in una versione iterativa, che di solito � pi� efficiente, in quanto non occorre mantenere lo stato della funzione una volta calcolata come � stato fatto nell'esempio precedente. Se l'algoritmo non � ricorsivo di coda, per trasformarlo in una versione iterativa occorre utilizzare un meccanismo di mantenimento dello stato analogo a quello che � utilizzato implicitamente nelle chiamate di funzione.